#include <iostream>
#include <stdio.h>
#include <ctime>
using namespace std;
//定义一个结构作为数据域
struct Student
{
     int id;         // 学号
    char name[20];  // 姓名
    int score;      // 入学分数
};
//定义单链表结构
typedef struct LNode
{
	Student data;             //结点的数据域
	struct LNode *next;   //结点的指针域
}LNode,*LinkList;	      //LinkList为指向结构体LNode的指针类型

//创建单链表L
bool InitList_L(LinkList &L)
{
L=new LNode;
L->next=NULL;
return true;		
}

//判断L是否为空表
 bool ListEmpty(LinkList L)
 {
 	if(L->next){//非空
	 	return false;
	 }
	 else return true;
 }
// 销毁单链表L
bool DestoryList_L(LinkList &L)
{
	LNode *p;
	while(L){
		p=L;
		L=L->next;
		delete p;
	}
	return true;
}

//清空链表，将L重置为空表
bool ClearList(LinkList &L)
{
	LNode*p,*q;//或者LinkList p,q;
	p=L->next;
	while(p){//没到表尾反复执行
		q=p->next;
		delete p;
		p=q;
		//类似用两块砖过河
	}
	L->next=NULL;
	return true;
}

//求单链表L的表长
int ListLength_L(LinkList L)
{int i;
LinkList p;
p=L->next;//p指向第一个结点
i=0;
while(p){  //遍历单链表，统计结点数
	i++;
	p=p->next;
}
	return i;
}
//获取线性表L中的某个数据元素的内容，通过变量返回
bool GetElem_L(LinkList L,int i,Student &e)
{
	//获取线性表L中的某个数据元素的内容，通过变量返回
		LinkList p;
		p=L->next;
		int j=1;
	while(p&&j<i){
		p=p->next;
		++j;
	}
	if(!p||j>i)	return false;
	e=p->data;
	return true;		
}
//在线性表L中查找值为e的数据元素
//找到，则返回L中值为e的数据元素的地址，查找失败返回NULL
LNode* LocateElem_L(LinkList L,int e)
{
	LinkList p;
	p=L->next;
	while(p&&p->data.id!=e){
		p=p->next;	
	}
return p;	
}
//在线性表L中查找值为e的数据元素的位置序号
int LocateElem_L2(LinkList L,int e)
{
	//返回L中值为e的数据元素的位置序号，查找失败返回0
	LinkList p;
	p=L->next;
	int j=1;
	while(p&&p->data.id!=e)
	{
		p=p->next;
		j++;
	}
	if(p) return j;
	else return 0;
}
//插入--在第i个结点前插入新结点，采用引用
bool LinkInsert_L(LinkList &L,int i)
{
	cout<<"请要输入插入同学的学号 姓名 分数 "<<endl;
	LinkList p;
	p=L;
	int j=0;
	while(p&&j<i-1){p=p->next;++j;}
	if(!p||j>i-1){return false;}
	LNode* s;   //s为新结点
	s=new LNode;
scanf("%d %s %d",&s->data.id,s->data.name,&s->data.score);
	s->next=p->next;
	p->next=s;
	return true;
}
//将线性表L中的第i个数据元素删除
bool ListDelete_L(LinkList &L,int i)
{
LinkList p=L;
int j=0;
while(p->next&&j<i-1){
	p=p->next;
	++j;
}	
if(!p->next||j>i-1)return false;
LinkList q;
q=p->next;
	p->next=q->next;
//	e=q->data;
	delete q;
	return true;	
}

//头插法建立链表 n(要输入)几个有效结点不包括头结点（虚空结点）
//(一条龙，里面包括了链表的初始化)
 void CreatList_H(LinkList &L,int n)
 {
 	LinkList p;
 	L=new LNode;
 	L->next=NULL;
 	for(int i=n;i>0;i--)
 	{
	 p=new LNode;
//cin>>p->data.id;
//cin>>p->data.name;
//cin>>p->data.score;
scanf("%d %s %d",&p->data.id,p->data.name,&p->data.score);
	 	p->next=L->next;
	 	L->next=p;
	 }
 }
 
 //尾插法建立单链表(一条龙，里面包括了链表的初始化)
  void CreatList_R(LinkList &L,int n)
  {
  	L=new LNode;
  	L->next=NULL;
  	LinkList r;
  	r=L;
  	LinkList p;
  	for(int i=0;i<n;i++)
  	{
 	 	p=new LNode;
 //	 	cin>>p->data;
scanf("%d %s %d",&p->data.id,p->data.name,&p->data.score);
 	 	p->next=NULL;
 	 	r->next=p;
 	 	r=p;
 	 }
  }
 
   //按顺序打印单链表
 void PrintList(LinkList L,int len)
 {
 	 printf("num\tname\t\score\n");
 	LNode *p;
 	p=L->next;
 	for(int j=1;j<=len;j++){
	 printf("%d\t%s\t%d\t\n",p->data.id,p->data.name,p->data.score);
	 	p=p->next;
	 }
	 	cout<<"链表数据域个数为"<<len<<endl;
 }
int main()
{
LinkList L;
InitList_L(L);
int i=1;
//增
while(1){
	LinkInsert_L(L,i);
	i++;
		printf("continue?Y/N\n");
		  	setbuf(stdin,NULL);
		  	 char choice=getchar(); 
		  	 if(choice=='n'||choice=='N'){
		  	 	break;
}
}
 PrintList(L,ListLength_L(L));
//删
cout<<"删除第三个学生"<<endl;
ListDelete_L(L,3);
PrintList(L,ListLength_L(L));
//查询学号为2的学生的信息
cout<<"查找学号为2的学生信息的位置，并返回地址："<<endl;
//查找2的位置，并返回地址
LNode* Locate=LocateElem_L(L,2);
cout<<Locate<<endl;
//查找2的位置，并返位置序号
cout<<"查找2的位置，并返位置序号："<<endl;
int s=LocateElem_L2(L,2);
cout<<s<<endl;;

	return 0;
}